using System.Collections.Generic;


namespace Super
{
	public class PriorityQueue<T> where T : IPriority<T>
	{
		public List<T> priorityQueue = new List<T>();
		public HashSet<T> queueCollection = new HashSet<T>();

		public void BuildPriorityQueue(List<T> nodes)
		{
			priorityQueue.Clear();
			priorityQueue = new List<T>(nodes);
			queueCollection.Clear();
			queueCollection = new HashSet<T>(nodes);

			int index = priorityQueue.Count / 2 - 1;
			while (index >= 0)
			{
				Heapify(index);
				index--;
			}
		}

		public void Heapify(int index)
		{
			int priorityIndex = index;
			int leftIndex = index * 2 + 1;
			int rightIndex = index * 2 + 2;

			bool hasLeft = leftIndex < priorityQueue.Count;
			if (hasLeft)
			{
				if (priorityQueue[leftIndex].Priority(priorityQueue[priorityIndex]))
					priorityIndex = leftIndex;
			}

			bool hasRight = rightIndex < priorityQueue.Count;
			if (hasRight)
			{
				if (priorityQueue[rightIndex].Priority(priorityQueue[priorityIndex]))
					priorityIndex = rightIndex;
			}

			if (priorityIndex != index)
			{
				GlobalUtil.ListSwap(priorityQueue, index, priorityIndex);
				Heapify(priorityIndex);
			}
		}

		public void Enqueue(T value)
		{
			if (queueCollection.Contains(value))
				return;

			priorityQueue.Add(value);
			queueCollection.Add(value);

			int index = priorityQueue.Count - 1;
			int parentIndex = (index - 1) / 2;
			bool isPriority = priorityQueue[index].Priority(priorityQueue[parentIndex]);

			while (parentIndex >= 0 && isPriority)
			{
				GlobalUtil.ListSwap(priorityQueue, index, parentIndex);

				index = parentIndex;
				parentIndex = (index - 1) / 2;
				isPriority = priorityQueue[index].Priority(priorityQueue[parentIndex]);
			}
		}

		public T Dequeue()
		{
			if (priorityQueue.Count == 0)
				return default(T);

			GlobalUtil.ListSwap(priorityQueue, 0, priorityQueue.Count - 1);
			T result = priorityQueue[priorityQueue.Count - 1];
			priorityQueue.RemoveAt(priorityQueue.Count - 1);
			queueCollection.Remove(result);

			Heapify(0);
			return result;
		}

		public T Peek()
		{
			if (priorityQueue.Count == 0)
				return default(T);

			return priorityQueue[0];
		}

		public bool TryPeek(out T node)
		{
			if (priorityQueue.Count == 0)
			{
				node = default(T);
				return false;
			}

			node = priorityQueue[0];
			return true;
		}

		public void Delete(T value)
		{
			if (!queueCollection.Contains(value))
				return;

			int index = 0;
			for (int i = 0; i < priorityQueue.Count; i++)
			{
				if (priorityQueue[i].Equals(value))
				{
					index = i;
					break;
				}
			}

			GlobalUtil.ListSwap(priorityQueue, index, priorityQueue.Count - 1);
			T result = priorityQueue[priorityQueue.Count - 1];
			priorityQueue.RemoveAt(priorityQueue.Count - 1);
			queueCollection.Remove(result);

			Heapify(index);
			return;
		}
	}

}
